package com.datastructures2.tree2;

import com.datastructures2.search.AvlTree;
import com.datastructures2.背包队列栈.Queue;

import java.util.Random;
import java.util.Scanner;

/**
 * AVL树
 * @author MaoLin Wang
 * @date 2020/2/1316:39
 */
public class AVLTree<T extends Comparable<? super T>> {

    private AVLNode<T> root;
    private static final int HEIGHT_DIFFERENCE=1;

    public AVLTree(AVLNode<T> root) {
        this.root = root;
    }

    /**
     * 删除数据
     * @param x
     */
    public void remove( T x )
    {
        root = remove( x, root );
        System.out.println("删除"+x+"旋转"+count+"次");
        count=0;
    }
    private AVLNode<T> remove(T data,AVLNode<T> root){

        if (root==null){
            return null;
        }
        int compareResult=data.compareTo(root.data);
        if (compareResult<0){
            root.left=remove(data,root.left);
        }else if (compareResult>0){
            root.right=remove(data,root.right);
        }else if (root.left!=null&&root.right!=null){
            //待删除节点有两个孩子
            root.data=findMin(root).data;
            root.right=remove(root.data,root.right);
        }else {
            //待删除节点没有孩子或有一个孩子
            root=root.left==null?root.right:root.left;
        }
        //重新平衡树
        return balance(root);
    }

    /**
     * 返回最小值
     * @return
     */
    public AVLNode<T> findMin(){
        return findMin(root);
    }
    private AVLNode<T> findMin(AVLNode<T> root){
        if (root==null){
            return null;
        }
        if (root.left==null){
            return root;
        }
        return findMin(root.right);
    }

    /**
     * 返回最大值
     * @return
     */
    public T findMax( )
    {
        if( isEmpty( ) )
            System.out.println("空");
        return findMax( root ).data;
    }

    private AVLNode<T> findMax( AVLNode<T> t )
    {
        if( t == null )
            return t;

        while( t.right != null )
            t = t.right;
        return t;
    }

    /**
     * 是否包含数据x
     * @param x
     * @return
     */
    public boolean contains( T x )
    {
        if (x==null)return false;
        return contains( x, root );
    }

    private boolean contains(T x, AVLNode<T> root) {
        if (root==null){
            return false;
        }
        int result=x.compareTo(root.data);
        if (result>0){
            return contains(x,root.right);
        }else if (result<0){
            return contains(x,root.left);
        }else {
            return true;
        }
    }

    public void makeEmpty( )
    {
        root = null;
    }
    public boolean isEmpty( )
    {
        return root == null;
    }

    /**
     * 返回数据队列
     * @return
     */
    public Queue<T>iterator(){
        if (isEmpty()){
            return null;
        }else {
            Queue<T>queue=new Queue<>();
           return iterator(root,queue);
        }
    }
    private Queue<T> iterator( AVLNode<T> t,Queue<T> queue )
    {
        if( t != null )
        {
             iterator( t.left,queue );
            queue.enqueue(t.data);
            iterator( t.right, queue);
        }
        return queue;
    }
    /**
     * 打印数据
     */
    public void printTree( )
    {
        if( isEmpty( ) )
            System.out.println( "Empty tree" );
        else
            printTree( root );
    }
    private void printTree( AVLNode<T> t )
    {
        if( t != null )
        {
            printTree( t.left );
            System.out.println( t.data );
            printTree( t.right );
        }
    }

    int count=0;
    /**
     * 插入一个数据
     * @param data
     */
    public void insert(T data){
        if (data==null){
            throw new IllegalArgumentException("数据为空");
        }
         root= insert(data, this.root);
        System.out.println("插入"+data+"旋转"+count+"次");
        count=0;
    }

    private AVLNode<T> insert(T data,AVLNode<T> t){
        if (t==null){
            return new AVLNode<>(data,null,null);
        }
        int compareResult=data.compareTo(t.data);
        if (compareResult<0){
            t.left=insert(data,t.left);
        }else if (compareResult>0){
            t.right=insert(data,t.right);
        }else {
            ;
        }
        return balance(t);
    }

    /**
     * 对节点t进行平衡
     * @param t
     * @return
     */
    private AVLNode<T> balance(AVLNode<T> t) {
        if (t==null){
            return null;
        }
        if (height(t.left)-height(t.right)>HEIGHT_DIFFERENCE){
            //左边高
            if (height(t.left.left)>=height(t.left.right)){
                //左子树的左子树高
                //此为情形1，在左子树的左子树插入了元素，直接右旋转
                t=rotateRight(t);
            }else {
                //左子树的右子树高
                //此为情形2，在左子树的右子树插入了元素，先左旋转再右旋转
                t=doubleLeftAndRight(t);
            }

        }else if (height(t.right)-height(t.left)>HEIGHT_DIFFERENCE){
            //右边高
            if (height(t.right.left)>height(t.right.right)){
                //右子树的左子树高了
                //此为情形3，在右子树的左子树插入了元素，先右旋转再左旋转
                t=doubleRightAndLeft(t);
            }else {
                //右子树的右子树高
                //此为情形4，在右子树的右子树插入了元素，直接左旋转
                t=rotateLeft(t);
            }
        }
        t.height=Math.max(height(t.left),height(t.right))+1;
        return t;

    }

    /**
     * 单旋转(右旋转)(情形1)
     * @param node
     * @return
     */
    private AVLNode<T>rotateRight(AVLNode<T> node){
        count++;
        AVLNode<T> left=node.left;
        node.left=left.right;
        left.right=node;
        node.height=Math.max(height(node.left),height(node.right))+1;
        left.height=Math.max(height(node.left),node.height)+1;
        return left;
    }

    /**
     * 单旋转(左旋转)(情形4)
     * @param node
     * @return
     */
    private AVLNode<T> rotateLeft(AVLNode<T> node){
        count++;
        AVLNode<T> right=node.right;
        node.right=right.left;
        right.left=node;
        node.height=Math.max(height(node.left),height(node.right))+1;
        right.height=Math.max(node.height,height(right.right))+1;
        return right;
    }

    /**
     * 双旋转(先左后右)(针对情形2)
     * @param node
     * @return
     */
    private AVLNode<T> doubleLeftAndRight(AVLNode<T> node){
        node.left=rotateLeft(node.left);
        return rotateRight(node);
    }

    /**
     * 双旋转(先右再左) (针对情形3)
     * @param node
     * @return
     */
    private AVLNode<T> doubleRightAndLeft(AVLNode<T> node){
        node.right=rotateRight(node.right);
        return rotateLeft(node);
    }
    private int height(AVLNode<T> t){
        return t==null?-1:t.height;
    }
    public static void main(String[] args) {
        AVLTree<String> tree = new AVLTree<>(new AVLNode<>("sdf"));
       /* Random random=new Random();
        long start=System.currentTimeMillis();

        long end=System.currentTimeMillis();
        System.out.println("插入800W数据时间："+(end-start));*/
        Random random=new Random();
        for (int i = 0; i < 1000000; i++) {
            tree.insert(random.nextInt(1000000)+"");

        }
        tree.remove("7777");
        tree.remove("2342");
        tree.remove("95643");
        tree.remove("78433");

     /*   Random random=new Random();
        long start=System.currentTimeMillis();
        for (int i = 0; i < 8000000; i++) {
            avlTree.insert(random.nextInt(8000000));
        }
        long end=System.currentTimeMillis();
        System.out.println("插入800W数据时间："+(end-start));
        Scanner scanner=new Scanner(System.in);
        int i = scanner.nextInt();
        long start2=System.currentTimeMillis();
        System.out.println(avlTree.contains(6000000));
        System.out.println(System.currentTimeMillis()-start2);*/

    }
}

class AVLNode<T>{
    AVLNode(T t){
        this(t,null,null);
    }
    AVLNode(T data,AVLNode<T> lt,AVLNode<T> rt){
        this.data=data;
        left=lt;
        right=rt;
        this.height=0;
    }

    T data;
    AVLNode<T> left;
    AVLNode<T> right;
    int height;


}